package com.fjh.algorithm.thought.sort;

/**
 * @author FJH
 * @date 2021/5/6 11:37
 *
 * 选择排序
 *
 * 从数组中选择最小元素，将它与数组的第一个元素交换位置。
 * 再从数组剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。
 * 不断进行这样的操作，直到将整个数组排序。
 *
 * 选择排序需要 N²/2 次比较和 N 次交换，它的运行时间与输入无关，
 * 这个特点使得它对一个已经排序的数组也需要这么多的比较和交换操作。
 */
public class SelectionSort {

    public static void sort(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            int min = i;
            for (int j = i+1; j < nums.length; j++) {
                if (nums[j] < nums[min]) {
                    min = j;
                }
            }
            Sort.swap(nums, i, min);
        }
    }

    /**
     * ### 基于切分的快速选择算法
     *
     * 快速排序的 partition() 方法，会返回一个整数 j 使得 a[l..j-1] 小于等于 a[j]，且 a[j+1..h] 大于等于 a[j]，此时 a[j] 就是数组的第 j 大元素。
     *
     * 可以利用这个特性找出数组的第 k 个元素。
     *
     * 该算法是线性级别的，假设每次能将数组二分，那么比较的总次数为 (N+N/2+N/4+..)，直到找到第 k 个元素，这个和显然小于 2N。
     */
    public int select(int[] nums, int k) {
        int l = 0, h = nums.length - 1;
        while (h > l) {
//            int j = partition(nums, l, h);
            int j = 0;
            if (j == k) {
                return nums[k];

            } else if (j > k) {
                h = j - 1;

            } else {
                l = j + 1;
            }
        }
        return nums[k];
    }
}
